import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 刘远望
 * Date: 2025-05-30
 * Time: 20:21
 */
//力扣 438 滑动窗口 找到字符串中所有字母异位次
public class Solution {
    //java哈希表实现
    public List<Integer> findAnagrams1(String s, String p) {
        //滑动窗口(窗口固定)
        Map<Character, Integer> hash1 = new HashMap<>();//s的hash表
        Map<Character, Integer> hash2 = new HashMap<>();//p的hash表

        char[] str = p.toCharArray();
        for (char x : str) {//将p的各个字符放进hash表
            hash2.put(x, hash2.getOrDefault(x, 0) + 1);
        }

        List<Integer> list = new ArrayList<>();
        for (int left = 0, right = 0; right < s.length(); right++) {
            char in = s.charAt(right);
            hash1.put(in, hash1.getOrDefault(in, 0) + 1);//进窗口

            if (right - left + 1 > p.length()) {//因为窗口固定所以用if判断
                char out = s.charAt(left);
                hash1.put(out, hash1.get(out) - 1);

                if (hash1.get(out) == 0) {
                    hash1.remove(out);//将字符值为0的键移除哈希表 以免影响后面判断
                }
                left++;//出窗口 -- 更新结果
            }
            if (hash1.equals(hash2)) {
                list.add(left);//更新结果
            }
        }
        return list;
    }

    //数组充当实现哈希表
    public List<Integer> findAnagrams2(String s, String p) {
        int m = s.length();
        int n = p.length();

        int[] hash1 = new int[30000];//数组模拟hash表 放s
        int[] hash2 = new int[30000];//数组模拟hash表 放p

        for (int i = 0; i < n; i++) {
            hash2[p.charAt(i) - 'a']++;//将p的字符作为下标统计个数
        }

        List<Integer> list = new ArrayList<>();
        for (int left = 0, right = 0; right < m; right++) {
            hash1[s.charAt(right) - 'a']++;//进窗口

            if (right - left + 1 > n) {//判断
                hash1[s.charAt(left) - 'a']--;
                left++;//出窗口
            }

            int flag = 1;
            for (int i = 0; i < 26; i++) {
                if (hash1[i] != hash2[i]) {
                    flag = 0;
                }
            }

            if (flag == 1) {
                list.add(left);//更新结果
            }
        }
        return list;
    }

    //维护count更新结果 速度最快
    public List<Integer> findAnagrams(String s, String p) {
        int m = s.length();
        int n = p.length();

        int[] hash1 = new int[30000];//数组模拟hash表 放s
        int[] hash2 = new int[30000];//数组模拟hash表 放p

        for (int i = 0; i < n; i++) {
            hash2[p.charAt(i) - 'a']++;//将p的字符作为下标统计个数
        }

        List<Integer> list = new ArrayList<>();
        for (int left = 0, right = 0; right < m; right++) {
            hash1[s.charAt(right) - 'a']++;//进窗口

            if (right - left + 1 > n) {//判断
                hash1[s.charAt(left) - 'a']--;
                left++;//出窗口
            }

            int flag = 1;
            for (int i = 0; i < 26; i++) {
                if (hash1[i] != hash2[i]) {
                    flag = 0;
                }
            }

            if (flag == 1) {
                list.add(left);//更新结果
            }
        }
        return list;
    }
}
